๐งท ์ต์ ๊ณตํต ์กฐ์
Lowest Common Ancestor ์๊ณ ๋ฆฌ์ฆ์ผ๋ก, ํธ๋ฆฌ์์ ๋ ์ ์ ์ด ๋ง๋๋ ์ต์ด ๋ถ๋ชจ ์ ์ ์ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
- ํธ๋ฆฌ ๋ฌธ์ ์์ ๊ณตํต ์กฐ์์ ์ฐพ์์ผ ํ๊ฑฐ๋, ์ ์ ๊ณผ ์ ์ ์ฌ์ด์ ์ด๋๊ฑฐ๋ฆฌ ๋๋ ๋ฐฉ๋ฌธ๊ฒฝ๋ก๋ฅผ ์ ์ฅํด์ผ ํ ๊ฒฝ์ฐ ์ฌ์ฉํ ์ ์๋ค.
๐ช ๊ณผ์
ํด๋น ์ ์ ์ depth ์ parent ๋ฅผ ์ ์ฅํ๋ ๋ฐฉ์์ด๋ค. ์ ๊ทธ๋ฆผ์์์ depth ์ parent ๋ ์๋์ ๊ฐ๋ค.
[depth : ์ ์ ]
0 -> 1
1 -> 2, 3
2 -> 4, 5, 6, 7
int[] parent = {0, 1, 1, 2, 2, 3, 3};
class Main {
// ์ ์ ๋ฒํธ๊ฐ 0๋ถํฐ ์์ํ๋ค๊ณ ๊ฐ์
// depth์ parent ์ด๊ธฐํ
static int[] depth = {0,1,1,2,2,2,2};
static int[] parent = {0,1,1,2,2,3,3};
public static void main(String[] args) {
int node1 = 3;
int node2 = 4;
int LCA = 0;
while(true){
if(depth[node1] == depth[node2]) {
// depth๊ฐ ๊ฐ์ ๊ฒฝ์ฐ
if(parent[node1] == parent[node2]) {
// ๋ถ๋ชจ๊ฐ ๊ฐ์ ๊ฒฝ์ฐ, LCA๋ฅผ ์ฐพ์
LCA = parent[node1];
break;
} else {
// ๋ถ๋ชจ๊ฐ ๋ค๋ฅด๊ธฐ์ ์์ ์ ์ ์ผ๋ก ์ด๋
node1 = parent[node1];
node2 = parent[node2];
}
} else {
// depth๊ฐ ๋ค๋ฅธ ๊ฒฝ์ฐ. ๋ ์์ depth์ ์ ์ ์ ์์๋ก ์ด๋
if (depth[node1] > depth[node2]) {
node1 = parent[node1];
} else {
node2 = parent[node2];
}
}
}
System.out.println("LCA is: " + LCA);
}
}
ํ์ง๋ง ์ ๋ฐฉ์์ 1์ธ๋ ๋ถ๋ชจ๋ง์ ๋ฐ๋ณตํด์ ์ฐพ์ ์ฌ๋ผ๊ฐ๊ธฐ ๋๋ฌธ์ ์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๊ฒ ๋๋ค. ์ด๋ฅผ ๊ฐ์ ํ๊ธฐ ์ํด "1, 2, 4, 8, ... ์นธ ๋จ์ด์ง ๋ถ๋ชจ๊ฐ ๋๊ตฐ์ง๋ ๊ธฐ๋ก"ํ์ฌ ์ฌ์ฉํ๋ค. ์ด๋ ์ ์๊ฐ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋ค.
๐ช ๊ฐ์ ๊ณผ์
1์ฐจ์ parent ๋ฐฐ์ด์, ๋ถ๋ชจ์ ์ ๋ณด๋ ์ ์ฅํ๊ธฐ ์ํด 2์ฐจ์ parent ๋ฐฐ์ด๋ก ๋ณ๊ฒฝํ๋ค.
parent[n][k](n = Tree์ ์ ์ ์, k = log(n)์ ์ฌ๋ฆผ)
๋จผ์ ์ฃผ์ด์ง tree์ root๋ฅผ ๊ฐ์ง๊ณ , DFS๋ฅผ ์ํํ๋ฉด์ ๊ฐ ์ ์ ๊ณผ ์ฐ๊ฒฐ๋ 1์ธ๋ ๋ถ๋ชจ์, ๊น์ด ์ ๋ณด๋ฅผ ๊ตฌํ๋ค.
int[][] parent = new int[n][k];
int[] depth = new int[n];
Arrays.fill(depth, -1);
void dfs(int cur) {
for (int next : adj[cur]) {
if (depth[next] == -1) {
parent[next][0] = cur;
depth[next] = depth[cur] + 1;
dfs(next);
}
}
return;
}
์ด์ ๊ตฌํ 1์ธ๋ ๋ถ๋ชจ ์ ๋ณด๋ฅผ ์ด์ฉํด, ๋ถ๋ชจ์ ์ ๋ณด๋ฅผ ๊ตฌํด์ผ ํ๋ค.
- ํ์ฌ๋ฅผ ๊ธฐ์ค์ผ๋ก 2()์นธ ๋จ์ด์ง ๋ถ๋ชจ๋ "ํ์ฌ์ 1()์นธ ๋จ์ด์ง ๋ถ๋ชจ์ 1()์นธ ๋จ์ด์ง ๋ถ๋ชจ"์ด๋ค.
- ํ์ฌ๋ฅผ ๊ธฐ์ค์ผ๋ก 4()์นธ ๋จ์ด์ง ๋ถ๋ชจ๋ "ํ์ฌ์ 2()์นธ ๋จ์ด์ง ๋ถ๋ชจ์ 2()์นธ ๋จ์ด์ง ๋ถ๋ชจ"์ด๋ค.
- ์ฆ, ํ์ฌ๋ฅผ ๊ธฐ์ค์ผ๋ก ์นธ ๋จ์ด์ง ๋ถ๋ชจ๋ ํ์ฌ์ ์นธ ๋จ์ด์ง ๋ถ๋ชจ์ ์นธ ๋จ์ด์ง ๋ถ๋ชจ์ด๋ค.
// max = logN์ ์ฌ๋ฆผ
void connectParents() {
for (int k = 1; k < max; k++) {
for (int cur = 1; cur <= n; cur++) {
parent[cur][k] = parent[parent[cur][k-1]][k-1];
}
}
}
์์ฑ๋ ์ ๋ณด๋ฅผ ์ด์ฉํ์ฌ, ์๋์ ๊ณผ์ ์ผ๋ก LCA๋ฅผ ์ฐพ๋๋ค.
- ๋ ์ ์ ์
depth๋ฅผ ๊ฐ๋๋ก ํ๋ค. - ๋ถ๋ชจ๊ฐ ๊ฐ์ ์ ์ ์ ๋๋ฌํ ๋๊น์ง ์๋ก ์ ํํ๋ค.
๋จผ์ ๋ ์ ์ ์ depth ๊ฐ ๊ฐ๋๋ก ํ๊ธฐ ์ํด, ๋ ์ ์ ๊ฐ์ depth ์ฐจ์ด๋ฅผ ๊ตฌํ๋ค.
-
depth์ ์ฐจ๊ฐ3์ด๋ผ๊ณ ๊ฐ์ ํ๋ฉด, ์ ํ๋ฅผ 2์ ์ง์๋ก ํ๊ธฐ์,3์ 2์ง์๋ก ๋ณํํ๋ค.3->11(2)์ผ๋ก ๋ํ๋ผ ์ ์๊ณ , ์ด๋ ์นธ์ง๋ฆฌ 1๋ฒ, ์นธ์ง๋ฆฌ 1๋ฒ ์ ํ๋ฅผ ์๋ฏธํ๋ค.- ๋ง์ฝ ์ฐจ๊ฐ
11์ด๋ผ๋ฉด,1011(2)๋ก ๋ํ๋ผ ์ ์๊ณ , ์ด๋ ์นธ์ง๋ฆฌ 1๋ฒ, ์นธ์ง๋ฆฌ 1๋ฒ, ์นธ์ง๋ฆฌ 1๋ฒ ์ ํ๋ฅผ ์๋ฏธํ๋ค.
int getLCA(int u, int v) {
// u๋ฅผ ๋ ๊น์ ์ ์ ์ผ๋ก!
if (depth[u] < depth[v]) swap(u, v);
int diffDist = depth[u] - depth[v];
for (int i = 0; diffDist != 0; i++) {
if (diffDist % 2 == 1) u = parent[u][i];
diffDist /= 2;
}
}
์ด์ depth ๊ฐ ๊ฐ์์ก๊ณ , ๋ถ๋ชจ๊ฐ ๊ฐ์ ์ ์ ์ ๋๋ฌํ ๋๊น์ง ๋ ์ ์ ์ ํจ๊ป ์ ํํ ๊ฒ์ด๋ค.
- ๋งํผ ๋ถ๋ชจ๋ฅผ ๊ฐ์ง๊ธฐ์, ํธ๋ฆฌ์ ์ ์ ์๋ณด๋ค ๋ ํฐ ๋ฒ์์ ๋ถ๋ชจ ์ ๋ณด๋ฅผ ๊ฐ์ง ์ ์๋ค. ์ด๋ -1๋ก ์ ์ฅ๋๋๋ก ํ๋ค. (๋ฉ๋ชจ๋ฆฌ์ ๋ญ๋น๋ฅผ ๋ง๊ธฐ ์ํด ์ต์ ํ๊ฐ ๊ฐ๋ฅํ ๊ฒ)
- ํฐ ๋ฒ์์ ๋ถ๋ชจ๋ถํฐ ๋ด๋ฆผ์ฐจ์์ผ๋ก (16, 8, 4, 2, 1) ๋ถ๋ชจ ์ ๋ณด๋ฅผ ํ์ธํ๋ฉด์ ์ ํํ๋ค.
-
์์์
diffDist๋งํผ ์ด๋ํ๋ ๊ฒ๊ณผ ๋น์ทํ ๋ฐฉ์์ผ๋ก ์ํํ๋๋ฐ, ๋์ฐฉ์ง๋ LCA ๋ฐ๋ก ๋ฐ์ ์์์ด๋ผ๊ณ ๊ฐ์ ํ๋ค.- ์ ํํ๋๋ฐ, ๋ ์ ์ ์ ๋ถ๋ชจ๊ฐ ๋์ผํ๋ค๋ฉด, ๋์ฐฉ์ง๋ฅผ ๋์ด๋ฒ๋ฆฐ ๊ฒฝ์ฐ์ด๊ณ ,
- ๋ถ๋ชจ์ ๊ฐ์ด -1์ด๋ผ๋ฉด ํธ๋ฆฌ์ ๋ฒ์๋ฅผ ๋ฒ์ด๋ ๊ฒฝ์ฐ์ด๋ค.
int getLCA(int u, int v) {
...
if (u != v) {
// ์ ํ ๊ฐ๋ฅํ ์ต๋๋ถํฐ ์์
for (int i = max - 1; i >= 0; i--) {
// -1์ด๋ผ๋ฉด ํธ๋ฆฌ์ ๋ฒ์ ๋ฐ, ๋ ๋ถ๋ชจ๊ฐ ๊ฐ๋ค๋ฉด LCA๊ฐ ์๋(๋์ฐฉ์ง๋ฅผ ๋์ด๋ฒ๋ฆฐ ๊ฒฝ์ฐ)
// ๊ทธ๋ ์ง ์์ ๊ฒฝ์ฐ์ ๋ํด ์ ํ๋ฅผ ์ํ, LCA์ ๋ฐ๋ก ๋ฐ ์ ์ ์ผ๋ก ์ ํ
if (parent[u][i] != -1 && parent[u][i] != parent[v][i]) {
u = parent[u][i];
v = parent[v][i];
}
}
// LCA ๋ฐ๋ก ๋ฐ ์ ์ ์ผ๋ก ์ ํํ๊ธฐ์, 1์นธ ์๊ฐ LCA
u = parent[u][0];
}
return u;
}